TNotes.leetcode

Appearance

0008. 字符串转换整数 (atoi)【中等】

0008. 字符串转换整数 (atoi)【中等】 ​

1. 📝 题目描述 ​

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数。

函数 myAtoi(string s) 的算法如下：

  1. 空格：读入字符串并丢弃无用的前导空格（" "）
  2. 符号：检查下一个字符（假设还未到字符末尾）为 '-' 还是 '+'。如果两者都不存在，则假定结果为正。
  3. 转换：通过跳过前置零来读取该整数，直到遇到非数字字符或到达字符串的结尾。如果没有读取数字，则结果为 0。
  4. 舍入：如果整数数超过 32 位有符号整数范围 [−231,231−1]，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被舍入为 −231，大于 231−1 的整数应该被舍入为 231−1。

返回整数作为最终结果。

示例 1：

txt
输入：s = "42"
输出：42

img

示例 2：

txt
输入：s = " -042"
输出：-42

img

示例 3：

txt
输入：s = "1337c0d3"
输出：1337

img

示例 4：

txt
输入：s = "0-1"
输出：0

img

示例 5：

txt
输入：s = "words and 987"
输出：0

解释：读取在第一个非数字字符“w”处停止。

提示：

  • 0 <= s.length <= 200
  • s 由英文字母（大写和小写）、数字（0-9）、' '、'+'、'-' 和 '.' 组成

2. 🎯 s.1 - 逐字符解析 ​

c
int myAtoi(char* s) {
    int i = 0;

    // 1. 跳过前导空格
    while (s[i] == ' ')
        i++;

    // 2. 判断符号
    int sign = 1;
    if (s[i] == '+' || s[i] == '-') {
        if (s[i] == '-')
            sign = -1;
        i++;
    }

    // 3. 读取数字，提前检查溢出
    int ans = 0;
    while (s[i] >= '0' && s[i] <= '9') {
        int digit = s[i] - '0';
        if (ans > (2147483647 - digit) / 10) {
            return sign == 1 ? 2147483647 : -2147483648;
        }
        ans = ans * 10 + digit;
        i++;
    }

    return sign * ans;
}
js
/**
 * @param {string} s
 * @return {number}
 */
var myAtoi = function (s) {
  const INT_MAX = 2 ** 31 - 1
  const INT_MIN = -(2 ** 31)

  let i = 0
  const n = s.length

  // 1. 跳过前导空格
  while (i < n && s[i] === ' ') i++

  // 2. 判断符号
  let sign = 1
  if (i < n && (s[i] === '+' || s[i] === '-')) {
    if (s[i] === '-') sign = -1
    i++
  }

  // 3. 读取数字
  let ans = 0
  while (i < n && s[i] >= '0' && s[i] <= '9') {
    const digit = s[i] - '0'
    // 提前检查溢出
    if (ans > Math.floor((INT_MAX - digit) / 10)) {
      return sign === 1 ? INT_MAX : INT_MIN
    }
    ans = ans * 10 + digit
    i++
  }

  return sign * ans
}
py
class Solution:
    def myAtoi(self, s: str) -> int:
        INT_MAX = 2**31 - 1
        INT_MIN = -(2**31)

        i, n = 0, len(s)

        # 1. 跳过前导空格
        while i < n and s[i] == " ":
            i += 1

        # 2. 判断符号
        sign = 1
        if i < n and s[i] in ("+", "-"):
            if s[i] == "-":
                sign = -1
            i += 1

        # 3. 读取数字，提前检查溢出
        ans = 0
        while i < n and s[i].isdigit():
            digit = int(s[i])
            if ans > (INT_MAX - digit) // 10:
                return INT_MAX if sign == 1 else INT_MIN
            ans = ans * 10 + digit
            i += 1

        return sign * ans
  • 时间复杂度：O(n)，其中 n 是字符串的长度，最多遍历一次
  • 空间复杂度：O(1)，只使用了常数级别的额外空间

算法思路：

  • 跳过前导空格，读取可选符号 +/-，逐字符读取数字直到遇到非数字字符或字符串结束
  • 每读入一位前先检查 ans > (INT_MAX - digit) / 10，防止溢出后再截断；满足则直接返回边界値

Discussions